 import java.util.ArrayList;
 import java.util.Comparator;
import java.util.PriorityQueue;

/*在面试的时候应该这样答

维护一个堆

*
具体思路参照leetcode官方解题
*/
public class Solution2 {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] ans = new int[k];
        if (k == 0) {    // 这个判断是为了节省时间，如果k为0就不需要建堆
            return ans;
        }
        /*
        * https://blog.csdn.net/hellokitty136/article/details/105831884
        * 重上面的博客看具体细节
        * 一句话：它的实现方式和堆是一样的，可作为堆来用:可以看作是一个会自动排序的队列
        * */
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override // 决定排序
            public int compare(Integer o1, Integer o2) {  /*重写比较器：o2-o1是从小到大排序
            o1-o2是从小到大排序。本题是需要小顶堆所以要从大到小排序：每次出队队首元素都是最大数那么剩下的就是最小的k个数
            怎么理解呢：就是把PriorityQueue看作堆，offer是入堆，poll是出堆，但poll是出最大的元素*/
                return o2 - o1;
            }
        });
        for (int i = 0; i < k; i++) {
            heap.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {  // 数组是length，字符串是length（），collection是size（）
            if (arr[i] < heap.element()) {

                heap.poll();
                heap.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            if (!heap.isEmpty()) {
                ans[i] = heap.poll();
            }
        }
        return ans;

    }

    // 牛客的题与方法与上面一样，但是更规范
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        int len = input.length;
        ArrayList<Integer> res = new ArrayList<>();
        if (len < k || k == 0) return res;
        PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare (Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        for (int i = 0; i < len; ++i) {
            heap.offer(input[i]);
            if (i > k-1) heap.poll();
        }
        for (int i = 0; i < k; ++i) {
            res.add(heap.poll());
        }
        return res;

    }

}



// 希望你开心点，一起加油！
/*
     _--_  _--_
    -    \/    -
     -        -
       -    -
         -

        _
       \   \
         \    \
         |     |
        /    /
       ... `

*/